#include<stdio.h>
#include<stdlib.h>
#define MAX_QUEUE 20
#define MAX_STACK 20

typedef struct node {
	int index;
	struct node * next;
}Node;

typedef struct edge {
	int start;
	int end;
	int type;//0 无向图。1 有向图
}Edge;

typedef struct queue{
	struct node * q[MAX_QUEUE];
	int start;
	int end;
}QUEUE;

typedef struct stack{
	struct node * s[MAX_STACK];
	int top;
}Stack;

Node * getNodeByIndex(int self,int start,int end);
void initNode(Node * n[],int num);
void initEdge(Edge * e[],int type);
void createList(Node * n[],Edge * e[],int nNum,int eNum);
void display(Node * n[]);
void createMatrix(int aMatrix[][5],Edge * e[]);
void displayArray(int aMatrix[][5]);
void BFS(Node * n[],Node *start);
QUEUE * initQueue();
void addQueue(QUEUE * queue,Node * start);
Node * popHeadQueue(QUEUE * queue);
int isEmptyQueue(QUEUE * queue);
void DFS(Node * n[],Node * start);
void visit(Stack * s, int flag[],Node * start,Node * n[]);
Stack * initStack();
void pushStack(Stack * stack,Node * node);
Node * popStack(Stack * stack);
int main(){
	Node * V[5];
	initNode(V,5);
	Edge * E[6];
	initEdge(E,0);
	createList(V,E,5,6);
	display(V);	
	printf("\n");
	int aMatrix[5][5] = {0};
	createMatrix(aMatrix,E);
	displayArray(aMatrix);
	printf("广度优先遍历\n");
	BFS(V,V[1]);
	printf("\n");
	printf("深度优先遍历\n");
	DFS(V,V[0]);
	printf("\n");
	DFS(V,V[1]);
	printf("\n");
	DFS(V,V[2]);
	printf("\n");
	DFS(V,V[3]);
	printf("\n");
	DFS(V,V[4]);
	printf("\n");
}
void DFS(Node * n[],Node * start){
	int flag[5] = {0};
	Stack * s = initStack();
	pushStack(s,start);
	while(s->top!=0){
		//visit(popStack(s),flag,start,n)
		visit(s,flag,popStack(s),n);
	}
}
Stack * initStack(){
	Stack * stack = (Stack*)malloc(sizeof(Stack));
	stack->top = 0;
	return stack;
}
void pushStack(Stack * stack,Node * node){
	if(stack->top<MAX_STACK)
		stack->s[stack->top++]=node;
}
Node * popStack(Stack * stack){
	if(stack->top > 0 && stack->top < MAX_STACK){
		return stack->s[--stack->top];
	}
	return NULL;
}
void visit(Stack * s, int flag[],Node * start,Node * n[]){
	Node * temp = start;
	if(flag[temp->index]!=1){
		printf("%d ",temp->index);
		flag[temp->index]= 1;
		pushStack(s,n[temp->index]);
		//将下一次的节点找到入栈
		temp=temp->next;
		while(temp!=NULL){
			if(flag[temp->index]!=1){
				pushStack(s,n[temp->index]);
				break;
			}
			temp = temp->next;
		}
	}else{
		temp = temp->next;
		while(temp){
			if(flag[temp->index]!=1){
				pushStack(s,n[temp->index]);
				break;
			}
			temp = temp->next;
		}
	}
	return;
}
QUEUE * initQueue(){
	QUEUE * q = (QUEUE*)malloc(sizeof(QUEUE));
	q->end = 0;
	q->start = 0;
	return q;
}
void addQueue(QUEUE * queue,Node * node){
	if(queue->end < MAX_QUEUE)
		queue->q[queue->end++] = node;
	return;
}

Node * popHeadQueue(QUEUE * queue){
	if(queue->start < MAX_QUEUE)
		return queue->q[queue->start++];
	return NULL;
}

int isEmptyQueue(QUEUE * queue){
	return queue->end - queue->start;
}


void BFS(Node * n[],Node * start){
	int flag[5] = {0};//记录那些点被访问
	QUEUE * q = initQueue();
	addQueue(q,start);
	flag[start->index] = 1;
	while(isEmptyQueue(q)!=0){//判断队列是否为空
		Node * temp = popHeadQueue(q);
		printf("%d ",temp->index);
		while(temp->next!=NULL){
			temp=temp->next;
			if(flag[temp->index]!=1){
				//addQueue(q,temp);error
				addQueue(q,n[temp->index]);
				flag[temp->index]=1;
			}
		}
	}

}
void createMatrix(int aMatrix[][5],Edge * e[]){
	for(size_t i = 0; i < 6; i++){
		if(e[i]->type==0){
			int start = e[i]->start;
			int end = e[i]->end;
			aMatrix[start][end] = 1;
			aMatrix[end][start] = 1;
		}else{
			int start = e[i]->start;
			int end = e[i]->end;
			aMatrix[start][end] = 1;
		}
	}
}
void displayArray(int aMatrix[][5]){
	for(size_t i = 0 ; i < 5 ; ++i){
		for(size_t j = 0 ; j < 5; j++){
			printf("%d ",aMatrix[i][j]);
		}
		printf("\n");
	}
}
void initNode(Node * n[],int num){
	for(size_t i = 0; i < num; ++i){
		Node * temp = (Node*)malloc(sizeof(Node));
		temp->index = i; 
		temp->next = NULL;
		n[i] = temp;
	}
}

void initEdge(Edge * e[],int type){
	if(type == 0){
		Edge * e1 = (Edge*)malloc(sizeof(Edge));
		e1->type = type;
		e1->start = 0;
		e1->end = 1;
		e[0] = e1;

		
		Edge * e2 = (Edge*)malloc(sizeof(Edge));
		e2->type = type;
		e2->start = 0;
		e2->end = 2;
		e[1] = e2;

		
		Edge * e3 = (Edge*)malloc(sizeof(Edge));
		e3->type = type;
		e3->start = 0;
		e3->end = 3;
		e[2] = e3;

		
		Edge * e4 = (Edge*)malloc(sizeof(Edge));
		e4->type = type;
		e4->start = 1;
		e4->end = 2;
		e[3] = e4;

		
		Edge * e5 = (Edge*)malloc(sizeof(Edge));
		e5->type = type;
		e5->start = 2;
		e5->end = 3;
		e[4] = e5;

		
		Edge * e6 = (Edge*)malloc(sizeof(Edge));
		e6->type = type;
		e6->start = 2;
		e6->end = 4;
		e[5] = e6;

	}else{
	}
}
void createList(Node * n[],Edge * e[],int nNum,int eNum){
	Node * temp;
	for(size_t i = 0 ; i < nNum; i++){
		temp = n[i];
		int index = temp->index;
		for(size_t j = 0 ; j < eNum; ++j){
			if(e[j]->type==0){
				if(e[j]->start==index||e[j]->end==index){
					temp->next = getNodeByIndex(index,e[j]->start,e[j]->end);
					temp = temp->next;
				}
			}else{
				if(e[j]->start==index){
					temp->next = getNodeByIndex(index,e[j]->start,e[j]->end);
					temp = temp->next;
				}
			}
		}
	}
}

Node * getNodeByIndex(int self,int start,int end){
	int index = self==start?end:start;
	Node * node = (Node*)malloc(sizeof(Node));
	node->index = index;
	node->next = NULL;
	return node;
}
void display(Node * n[]){
	for(size_t i = 0 ; i<5; i++){
		Node * temp = n[i];
		while(temp!=NULL){
			printf("%d ",temp->index);
			temp=temp->next;
		}
		printf("\n");
	}
}
